package my;

import utils.Tools;

/**
 * 斐波那契数列
 *
 * @author AJun
 * @date 2020/11/15
 */
public class Fib {

    public static void main(String[] args) {
        Fib fib = new Fib();
        int n = 40;
        Tools.calcTime("fib0", () -> System.out.println(fib.fib0(n)));
        Tools.calcTime("fib1", () -> System.out.println(fib.fib1(n)));
        Tools.calcTime("fib2", () -> System.out.println(fib.fib2(n)));
        Tools.calcTime("fib3", () -> System.out.println(fib.fib3(n)));
        Tools.calcTime("fib4", () -> System.out.println(fib.fib4(n)));
        Tools.calcTime("fib5", () -> System.out.println(fib.fib5(n)));
        Tools.calcTime("fib6", () -> System.out.println(fib.fib6(n)));
    }

    /**
     * 普通递归 fib
     * 时间复杂度: O(2^n)
     * 空间复杂度: O(n)
     */
    int fib0(int n) {
        if (n <= 2) return 1;
        return fib0(n - 1) + fib0(n - 2);
    }

    /**
     * fib 优化: 记忆化(fib0 中出现很多重复计算，可以使用数组存放计算过的结果)
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     */
    int fib1(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[2] = array[1] = 1;
        return fib(array, n);
    }

    int fib(int[] array, int n) {
        if (array[n] == 0) {
            array[n] = fib(array, n - 1) + fib(array, n - 2);
        }
        return array[n];
    }

    /**
     * fib 优化: 去除递归调用
     * 时间复杂度: O(n)
     * 空间复杂度: O(n)
     */
    int fib2(int n) {
        if (n <= 2) return 1;
        int[] array = new int[n + 1];
        array[2] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i] = array[i - 1] + array[i - 2];
        }
        return array[n];
    }

    /**
     * fib 优化: 由于每次运算只需要用到数组中的 2 个元素，所以可以使用滚动数组来优化
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    int fib3(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i % 2] = array[(i - 1) % 2] + array[(i - 2) % 2];
        }
        return array[n % 2];
    }

    /**
     * fib 优化: 乘、除、模运算效率较低，建议用其他方式取代(x%2 = x&1(注意只有是模 2 才可以))
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    int fib4(int n) {
        if (n <= 2) return 1;
        int[] array = new int[2];
        array[0] = array[1] = 1;
        for (int i = 3; i <= n; i++) {
            array[i & 1] = array[(i - 1) & 1] + array[(i - 2) & 1];
        }
        return array[n & 2];
    }

    /**
     * fib 优化: 只用到数组的俩个元素，不如直接使用俩个变量
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    int fib5(int n) {
        if (n <= 2) return 1;
        int first = 1;
        int second = 1;
        for (int i = 3; i <= n; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * fib 优化: 斐波那契数列有个线性代数解法(特征方程)
     * 复杂度取决于 pow 函数，至少可以低至 O(logn)
     */
    int fib6(int n) {
        double c = Math.sqrt(5);
        return (int) ((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
    }

}
